{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Chap6 Stacks&Queues&Deques"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2019-07-16T08:52:39.317446Z",
     "start_time": "2019-07-16T08:52:39.314039Z"
    }
   },
   "outputs": [],
   "source": [
    "from pyds.Stack import ArrayStack\n",
    "from collections import deque"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Reinforcement"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### R-6.1\n",
    "What values are returned during the following series of stack operations, if\n",
    "executed upon an initially empty stack? push(5), push(3), pop(), push(2),\n",
    "push(8), pop(), pop(), push(9), push(1), pop(), push(7), push(6), pop(),\n",
    "pop(), push(4), pop(), pop()."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2019-07-16T08:52:57.608951Z",
     "start_time": "2019-07-16T08:52:57.599390Z"
    }
   },
   "outputs": [],
   "source": [
    "s = ArrayStack()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2019-07-16T08:53:03.603287Z",
     "start_time": "2019-07-16T08:53:03.592821Z"
    }
   },
   "outputs": [],
   "source": [
    "s.push(5)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2019-07-16T08:53:08.105308Z",
     "start_time": "2019-07-16T08:53:08.096144Z"
    }
   },
   "outputs": [],
   "source": [
    "s.push(3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2019-07-16T08:53:13.211080Z",
     "start_time": "2019-07-16T08:53:13.189691Z"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "s.pop()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2019-07-16T08:53:53.345838Z",
     "start_time": "2019-07-16T08:53:53.336817Z"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "|   2   |\n",
       "---------\n",
       "|   5   |\n",
       "---------"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "s"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Note that:\n",
    "```\n",
    "push -> None\n",
    "pop  -> top element | Empty Error\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### R-6.2\n",
    "Suppose an initially empty stack S has executed a total of 25 push opera-\n",
    "tions, 12 top operations, and 10 pop operations, 3 of which raised Empty\n",
    "errors that were caught and ignored. What is the current size of S?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "25 - 10 + 3 = 18"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### R-6.3 \n",
    "Implement a function with signature transfer(S, T) that transfers all ele-\n",
    "ments from stack S onto stack T, so that the element that starts at the top\n",
    "of S is the first to be inserted onto T, and the element at the bottom of S\n",
    "ends up at the top of T."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2019-07-16T08:55:01.746994Z",
     "start_time": "2019-07-16T08:55:01.736897Z"
    }
   },
   "outputs": [],
   "source": [
    "def transfer(S: ArrayStack, T: ArrayStack) -> None:\n",
    "    while not S.is_empty():\n",
    "        T.push(S.pop())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2019-07-16T08:55:06.747530Z",
     "start_time": "2019-07-16T08:55:06.735776Z"
    }
   },
   "outputs": [],
   "source": [
    "def test_transfer():\n",
    "    S = ArrayStack()\n",
    "    S.push(3)\n",
    "    S.push(2)\n",
    "    S.push(1)\n",
    "    print(S)\n",
    "    T = ArrayStack()\n",
    "    transfer(S, T)\n",
    "    print(T)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2019-07-16T08:55:09.856707Z",
     "start_time": "2019-07-16T08:55:09.842789Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "|   1   |\n",
      "---------\n",
      "|   2   |\n",
      "---------\n",
      "|   3   |\n",
      "---------\n",
      "\n",
      "|   3   |\n",
      "---------\n",
      "|   2   |\n",
      "---------\n",
      "|   1   |\n",
      "---------\n",
      "\n"
     ]
    }
   ],
   "source": [
    "test_transfer()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### R-6.4\n",
    "Give a recursive method for removing all the elements from a stack."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2019-07-16T08:55:44.250875Z",
     "start_time": "2019-07-16T08:55:44.241517Z"
    }
   },
   "outputs": [],
   "source": [
    "def stack_clear(s: ArrayStack) -> None:\n",
    "    if s.is_empty():\n",
    "        return\n",
    "    s.pop()\n",
    "    return stack_clear(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2019-07-16T08:55:50.512574Z",
     "start_time": "2019-07-16T08:55:50.504879Z"
    }
   },
   "outputs": [],
   "source": [
    "def test_stack_clear():\n",
    "    S = ArrayStack()\n",
    "    S.push(3)\n",
    "    S.push(2)\n",
    "    S.push(1)\n",
    "    print(S)\n",
    "    stack_clear(S)\n",
    "    print(S)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2019-07-16T08:55:54.054673Z",
     "start_time": "2019-07-16T08:55:54.049474Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "|   1   |\n",
      "---------\n",
      "|   2   |\n",
      "---------\n",
      "|   3   |\n",
      "---------\n",
      "\n",
      "|       |\n",
      "---------\n"
     ]
    }
   ],
   "source": [
    "test_stack_clear()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### R-6.5 \n",
    "Implement a function that reverses a list of elements by pushing them onto\n",
    "a stack in one order, and writing them back to the list in reversed order."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2019-07-16T08:56:15.818707Z",
     "start_time": "2019-07-16T08:56:15.805601Z"
    }
   },
   "outputs": [],
   "source": [
    "def reverse_list(items):\n",
    "    s = ArrayStack()\n",
    "    for item in items:\n",
    "        s.push(item)\n",
    "    for i in range(len(items)):\n",
    "        items[i] = s.pop()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2019-07-16T08:56:19.932316Z",
     "start_time": "2019-07-16T08:56:19.924976Z"
    }
   },
   "outputs": [],
   "source": [
    "def test_reverse_list():\n",
    "    items = [1, 2, 3]\n",
    "    reverse_list(items)\n",
    "    print(items)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2019-07-16T08:56:23.809728Z",
     "start_time": "2019-07-16T08:56:23.799228Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[3, 2, 1]\n"
     ]
    }
   ],
   "source": [
    "test_reverse_list()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### R-6.7 \n",
    "What values are returned during the following sequence of queue opera-\n",
    "tions, if executed on an initially empty queue? enqueue(5), enqueue(3),\n",
    "dequeue(), enqueue(2), enqueue(8), dequeue(), dequeue(), enqueue(9),\n",
    "enqueue(1), dequeue(), enqueue(7), enqueue(6), dequeue(), dequeue(),\n",
    "enqueue(4), dequeue(), dequeue()."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Note that:\n",
    "```\n",
    "enqueue -> None\n",
    "dequeue -> first element | Empty Error\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### R-6.8\n",
    "Suppose an initially empty queue Q has executed a total of 32 enqueue\n",
    "operations, 10 first operations, and 15 dequeue operations, 5 of which\n",
    "raised Empty errors that were caught and ignored. What is the current\n",
    "size of Q?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "32 - 15 + 5 = 22"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### R-6.9\n",
    "Had the queue of the previous problem been an instance of ArrayQueue\n",
    "that used an initial array of capacity 30, and had its size never been greater\n",
    "than 30, what would be the final value of the front instance variable?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "15 - 5 = 10"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### R-6.11\n",
    "Give a simple adapter that implements our queue ADT while using a\n",
    "collections.deque instance for storage."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2019-07-16T08:58:24.860183Z",
     "start_time": "2019-07-16T08:58:24.849093Z"
    }
   },
   "outputs": [],
   "source": [
    "class AdapterQueue:\n",
    "    def __init__(self):\n",
    "        self._queue = deque()\n",
    "\n",
    "    def __len__(self):\n",
    "        return len(self._queue)\n",
    "\n",
    "    def first(self):\n",
    "        return self._queue[0]\n",
    "\n",
    "    def is_empty(self):\n",
    "        return len(self._queue) == 0\n",
    "\n",
    "    def enqueue(self, e):\n",
    "        self._queue.append(e)\n",
    "\n",
    "    def dequeue(self):\n",
    "        self._queue.popleft()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Creativity"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### C-6.15 \n",
    "Suppose Alice has picked three distinct integers and placed them into a\n",
    "stack S in random order. Write a short, straight-line piece of pseudo-code\n",
    "(with no loops or recursion) that uses only one comparison and only one\n",
    "variable x, yet that results in variable x storing the largest of Alice’s three\n",
    "integers with probability 2/3. Argue why your method is correct."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "`x = max(S.pop(), S.pop())`\n",
    "\n",
    "Note: we can assume the three numbers are: 1, 2, 3. Then,\n",
    "we draw two numbers from them, there are three situations:\n",
    "(1, 2), (1, 3), (2, 3). Using our algorithm, we will get\n",
    "2, 3, 3, then x storing the largest of Alice’s three\n",
    "integers with probability 2/3."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### C-6.16\n",
    "Modify the ArrayStack implementation so that the stack’s capacity is lim-\n",
    "ited to maxlen elements, where maxlen is an optional parameter to the\n",
    "constructor (that defaults to None). If push is called when the stack is at\n",
    "full capacity, throw a Full exception (defined similarly to Empty)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2019-07-16T08:59:55.280261Z",
     "start_time": "2019-07-16T08:59:55.271992Z"
    }
   },
   "outputs": [],
   "source": [
    "# C-6.16\n",
    "class Full(Exception):\n",
    "    pass\n",
    "\n",
    "\n",
    "class ArrayStackMax(ArrayStack):\n",
    "    def __init__(self, maxlen=None):\n",
    "        self._data = []\n",
    "        self._maxlen = maxlen\n",
    "\n",
    "    def push(self, e):\n",
    "        if len(self._data) >= self._maxlen:\n",
    "            raise Full(\"Reached the max length restriction!\")\n",
    "        self.push(e)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### C-6.17 \n",
    "In the previous exercise, we assume that the underlying list is initially\n",
    "empty. Redo that exercise, this time preallocating an underlying list with\n",
    "length equal to the stack’s maximum capacity."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2019-07-16T09:00:18.095516Z",
     "start_time": "2019-07-16T09:00:18.089877Z"
    }
   },
   "outputs": [],
   "source": [
    "class ArrayStackInitList(ArrayStack):\n",
    "    def __init__(self, maxlen=None):\n",
    "        self._data = [None] * maxlen\n",
    "        self._maxlen = maxlen"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### C-6.18 \n",
    "Show how to use the transfer function, described in Exercise R-6.3, and\n",
    "two temporary stacks, to replace the contents of a given stack S with those\n",
    "same elements, but in reversed order."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2019-07-16T09:00:46.785770Z",
     "start_time": "2019-07-16T09:00:46.780637Z"
    }
   },
   "outputs": [],
   "source": [
    "def reverse_stack(S: ArrayStack):\n",
    "    s1 = ArrayStack()\n",
    "    s2 = ArrayStack()\n",
    "    transfer(S, s1)\n",
    "    transfer(s1, s2)\n",
    "    transfer(s2, S)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2019-07-16T09:00:52.890722Z",
     "start_time": "2019-07-16T09:00:52.882929Z"
    }
   },
   "outputs": [],
   "source": [
    "def test_reverse_stack():\n",
    "    S = ArrayStack()\n",
    "    S.push(3)\n",
    "    S.push(2)\n",
    "    S.push(1)\n",
    "    print(S)\n",
    "    reverse_stack(S)\n",
    "    print(S)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2019-07-16T09:01:03.263016Z",
     "start_time": "2019-07-16T09:01:03.259338Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "|   1   |\n",
      "---------\n",
      "|   2   |\n",
      "---------\n",
      "|   3   |\n",
      "---------\n",
      "\n",
      "|   3   |\n",
      "---------\n",
      "|   2   |\n",
      "---------\n",
      "|   1   |\n",
      "---------\n",
      "\n"
     ]
    }
   ],
   "source": [
    "test_reverse_stack()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### C-6.23 \n",
    "Suppose you have three nonempty stacks R, S, and T . Describe a sequence\n",
    "of operations that results in S storing all elements originally in T below all\n",
    "of S’s original elements, with both sets of those elements in their original\n",
    "order. The final configuration for R should be the same as its original\n",
    "configuration. For example, if R = [1, 2, 3], S = [4, 5], and T = [6, 7, 8, 9],\n",
    "the final configuration should have R = [1, 2, 3] and S = [6, 7, 8, 9, 4, 5]."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2019-07-16T09:01:31.780860Z",
     "start_time": "2019-07-16T09:01:31.773061Z"
    }
   },
   "outputs": [],
   "source": [
    "def three_stack(R: ArrayStack, S: ArrayStack, T: ArrayStack):\n",
    "    R_len = len(R)\n",
    "    while not S.is_empty():\n",
    "        R.push(S.pop())\n",
    "    while not T.is_empty():\n",
    "        R.push(T.pop())\n",
    "    while len(R) > R_len:\n",
    "        S.push(R.pop())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2019-07-16T09:01:43.542893Z",
     "start_time": "2019-07-16T09:01:43.532999Z"
    }
   },
   "outputs": [],
   "source": [
    "def test_three_stack():\n",
    "    R = ArrayStack()\n",
    "    R.push(1)\n",
    "    R.push(2)\n",
    "    R.push(3)\n",
    "\n",
    "    S = ArrayStack()\n",
    "    S.push(4)\n",
    "    S.push(5)\n",
    "\n",
    "    T = ArrayStack()\n",
    "    T.push(6)\n",
    "    T.push(7)\n",
    "    T.push(8)\n",
    "    T.push(9)\n",
    "\n",
    "    three_stack(R, S, T)\n",
    "    print(\"R:\")\n",
    "    print(R)\n",
    "    print(\"S:\")\n",
    "    print(S)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2019-07-16T09:01:50.142288Z",
     "start_time": "2019-07-16T09:01:50.133420Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "R:\n",
      "|   3   |\n",
      "---------\n",
      "|   2   |\n",
      "---------\n",
      "|   1   |\n",
      "---------\n",
      "\n",
      "S:\n",
      "|   5   |\n",
      "---------\n",
      "|   4   |\n",
      "---------\n",
      "|   9   |\n",
      "---------\n",
      "|   8   |\n",
      "---------\n",
      "|   7   |\n",
      "---------\n",
      "|   6   |\n",
      "---------\n",
      "\n"
     ]
    }
   ],
   "source": [
    "test_three_stack()"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.3"
  },
  "toc": {
   "nav_menu": {},
   "number_sections": false,
   "sideBar": true,
   "skip_h1_title": false,
   "title_cell": "Table of Contents",
   "title_sidebar": "Contents",
   "toc_cell": false,
   "toc_position": {},
   "toc_section_display": true,
   "toc_window_display": false
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
